Search results for "Partial Order"
showing 10 items of 10 documents
Stubborn sets, frozen actions, and fair testing
2021
Many partial order methods use some special condition for ensuring that the analysis is not terminated prematurely. In the case of stubborn set methods for safety properties, implementation of the condition is usually based on recognizing the terminal strong components of the reduced state space and, if necessary, expanding the stubborn sets used in their roots. In an earlier study it was pointed out that if the system may execute a cycle consisting of only invisible actions and that cycle is concurrent with the rest of the system in a non-obvious way, then the method may be fooled to construct all states of the full parallel composition. This problem is solved in this study by a method tha…
Ordering and Convex Polyominoes
2005
We introduce a partial order on pictures (matrices), denoted by ≼ that extends to two dimensions the subword ordering on words. We investigate properties of special families of discrete sets (corresponding to {0,1}-matrices) with respect to this partial order. In particular we consider the families of polyominoes and convex polyominoes and the family, recently introduced by the authors, of L-convex polyominoes. In the first part of the paper we study the closure properties of such families with respect to the order. In particular we obtain a new characterization of L-convex polyominoes: a discrete set P is a L-convex polyomino if and only if all the elements Q≼P are polyominoes. In the seco…
Completeness number of families of subsets of convergence spaces
2016
International audience; Compactoid and compact families generalize both convergent filters and compact sets. This concept turned out to be useful in various quests, like Scott topologies, triquotient maps and extensions of the Choquet active boundary theorem.The completeness number of a family in a convergence space is the least cardinality of collections of covers for which the family becomes complete. 0-completeness amounts to compactness, finite completeness to relative local compactness and countable completeness to Čech completeness. Countably conditional countable completeness amounts to pseudocompleteness of Oxtoby. Conversely, each completeness class of families can be represented a…
The Inconsistent Labelling Problem of Stutter-Preserving Partial-Order Reduction
2020
AbstractIn model checking, partial-order reduction (POR) is an effective technique to reduce the size of the state space. Stubborn sets are an established variant of POR and have seen many applications over the past 31 years. One of the early works on stubborn sets shows that a combination of several conditions on the reduction is sufficient to preserve stutter-trace equivalence, making stubborn sets suitable for model checking of linear-time properties. In this paper, we identify a flaw in the reasoning and show with a counter-example that stutter-trace equivalence is not necessarily preserved. We propose a solution together with an updated correctness proof. Furthermore, we analyse in whi…
An approximate fixed point result for multivalued mappings under two constraint inequalities
2017
We consider an approximate multivalued fixed point problem under two constraint inequalities, for which we provide sufficient conditions for the existence of at least one solution. Then, we present some consequences and related results.
Nonlinear contractions involving simulation functions in a metric space with a partial order
2015
Very recently, Khojasteh, Shukla and Radenovic [F. Khojasteh, S. Shukla, S. Radenovic, Filomat, 29 (2015), 1189-1194] introduced the notion of Z-contraction, that is, a nonlinear contraction involving a new class of mappings namely simulation functions. This kind of contractions generalizes the Banach contraction and unifies several known types of nonlinear contractions. In this paper, we consider a pair of nonlinear operators satisfying a nonlinear contraction involving a simulation function in a metric space endowed with a partial order. For this pair of operators, we establish coincidence and common fixed point results. As applications, several related results in fixed point theory in a …
A Detailed Account of The Inconsistent Labelling Problem of Stutter-Preserving Partial-Order Reduction
2021
One of the most popular state-space reduction techniques for model checking is partial-order reduction (POR). Of the many different POR implementations, stubborn sets are a very versatile variant and have thus seen many different applications over the past 32 years. One of the early stubborn sets works shows how the basic conditions for reduction can be augmented to preserve stutter-trace equivalence, making stubborn sets suitable for model checking of linear-time properties. In this paper, we identify a flaw in the reasoning and show with a counter-example that stutter-trace equivalence is not necessarily preserved. We propose a stronger reduction condition and provide extensive new correc…
Patterns in words and languages
2004
AbstractA word p, over the alphabet of variables E, is a pattern of a word w over A if there exists a non-erasing morphism h from E∗ to A∗ such that h(p)=w. If we take E=A, given two words u,v∈A∗, we write u⩽v if u is a pattern of v. The restriction of ⩽ to aA∗, where A is the binary alphabet {a,b}, is a partial order relation. We introduce, given a word v, the set P(v) of all words u such that u⩽v. P(v), with the relation ⩽, is a poset and it is called the pattern poset of v. The first part of the paper is devoted to investigate the relationships between the structure of the poset P(v) and the combinatorial properties of the word v. In the last section, for a given language L, we consider …
The diamond partial order in rings
2013
In this paper we introduce a new partial order on a ring, namely the diamond partial order. This order is an extension of a partial order defined in a matrix setting in [J.K. Baksalary and J. Hauke, A further algebraic version of Cochran's theorem and matrix partial orderings, Linear Algebra and its Applications, 127, 157--169, 1990]. We characterize the diamond partial order on rings and study its relationships with other partial orders known in the literature. We also analyze successors, predecessors and maximal elements under the diamond order.
A fuzzy approach to multidimensional material deprivation measurement: the case of foreigners living in Italy
2014
This paper provides a new approach to the measurement of multidimensional material deprivation, based on partial order theory and on fuzzy set measurement. The main feature of the methodology is that the information needed for the deprivation assessment is extracted directly from the relational structure of the dataset, avoiding any kind of scaling and not proper aggregation procedure, so as to respect the measurement level of the data. An empirical illustration, using data from a special EU-SILC survey on migrants in Italy, provides a new insight on the material deprivation of foreigners living in Italy